1. Field of the Invention
The present invention relates to packet shapers that shape packets to transmission bandwidth.
2. Description of Related Art
In a packet mode communication method used for internets, because packets from many users can be transmitted in common over a same transmission line, the transmission cost per bandwidth can be decreased. Meanwhile, internet users have made a demand that Quality of Service (QoS) such as reduced delay time and a low packet discard rate that were implemented for conventional telephone networks and corporate private networks should also be implemented in internet operation.
Guaranteed minimum bandwidth service, one QoS implementation service, is such that the carrier guarantees packet transmission within minimum bandwidth assigned by contract to each user (contractor with the carrier) and transfers packets in excess of the minimum bandwidth as long as the network resources permit them.
In an internet 200, for example, as shown in FIG. 2, the guaranteed minimum bandwidth service is provided. Assume that five terminals (terminal E 235, terminal F 236, terminal G 237, terminal H 238, and terminal I 239) that are directly connected to an edge router B 204 surely receive packets within terminal-specific minimum bandwidth that has been assigned by contract to user E, user F, user G, user H, and user I, respectively. Traffic sent from terminal A 231, terminal B232, terminal C 233, and terminal D 234 that are directly connected to an edge router A 201 is transferred via the edge router 201, a backbone router A 202, a backbone router 203, and the edge router B 204 to the terminal E 235, terminal F 236, terminal G 237, terminal H 238, and terminal I 239. If a line from the backbone router B 203 to the edge router B 204 is bottlenecking, the backbone router B 203 has a packet shaper for the line and ensures that traffic falling within the minimum bandwidth specific to each user is transferred to its destination.
As a scheduling method of the packet shaper that ensures packet transmission within minimum bandwidth, for example, the scheduling method called Weighted Fair Queuing (WFQ) is known. An algorithm of WFQ, called Self Clocked Fair Queuing (SCFQ) is described by S. Golestani, A Self-Clocked Fair Queuing Scheme for Broadband Applications, In proc. of INFORCOM94, pp. 636-646, 1994. Previous packet shapers of related art have a plurality of queues i (where i=1 to N) and each queue i has weight Wi and variable Fi in proportion to the bandwidth in use. When a packet arrives at the packet shaper, the variable Fi is updated. When sending out a packet, the first packet is output for service from the queue i with the minimum variable Fi among the variables Fi of the first packets in the queues i in which packets are stored. Variable Fi update is executed, according to the following equation:Fi=L/Wi+max(Fi, V(ta))where, L is length of an arrived packet, ta is time of arrival of the packet, V(t) is a function that returns a value of the packet variable Fi of queue i at time t. In this scheme, for packets from queue i, the minimum bandwidth for Wi/(total sum of values of Wi)×line bandwidth is ensured.